package com.sicheng.lc.周赛.分类.堆;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/22 21:27
 */
@SuppressWarnings("all")
public class K次增加后的最大乘积 {
    //    https://leetcode.cn/problems/maximum-product-after-k-increments/

    public int maximumProduct(int[] nums, int k) {
        int mod = (int) 1e9 + 7;
        heap(nums);
        while (k-- > 0) {
            nums[0] = (nums[0] + 1) % mod;
            shiftDown(nums, nums[0], 0);
        }
        long res = 1;

        for (int num : nums) {
            res = res * num % mod;
        }
        return (int) res;
    }

    void heap(int[] nums) {
        for (int i = (nums.length >> 1) - 1; i >= 0; i--) {
            shiftDown(nums, nums[i], i);
        }
    }

    void shiftDown(int[] nums, int e, int k) {
        int half = nums.length >> 1;
        while (k < half) {
            int child = k << 1 | 1;
            if (child + 1 < nums.length && nums[child + 1] < nums[child]) {
                child++;
            }

            if (nums[child] >= e) {
                break;
            }
            nums[k] = nums[child];
            k = child;

        }

        nums[k] = e;
    }

    public static void main(String[] args) {

        K次增加后的最大乘积 solution = new K次增加后的最大乘积();
        int[] nums = {6, 3, 3, 2};
        int k = 2;
        System.out.println(solution.maximumProduct(nums, k));
    }
}
